// 给定长度为n+1的整数数组nums，数组范围为[1,n]，已知数组内存在一个唯一重复的整数，求找出这个整数。
// 条件：
// 1、数组不能被修改
// 2、空间复杂度为O1
// 3、时间复杂度要求小于On
// 4、该重复数可能不止重复一次。

var findDuplicate: (nums: number[]) => number = function (nums) {
    // 声明左右区间
    let left: number = 1;
    let right: number = nums.length - 1;
    // 二分搜索算法用于划定区间
    while (left < right) {
        let mid: number = Math.floor((left + right) / 2);
        let count: number = 0;
        // 统计有多少个元素小于或等于mid
        for (let num of nums) {
            count = num <= mid ? count + 1 : count;
        }
        // 根据抽屉原理判断重复数落于哪个区间
        if (count > mid) {
            right = mid;
        } else {
            left = mid + 1;
        }
    }
    // 出口时left = right
    return left;
};

        // 首先需要复习一个小学奥数原理：抽屉原理
        // 简单来说就是已知有1-9号抽屉，如果我要往里面放10个苹果，那么肯定会有一个抽屉装的超过1个苹果
        // 已知题目给的数组范围在[1,n](我们看成是n个抽屉，n+1个苹果），
        // 那么我们采用二分搜索算法，假设一个中间数mid，
        // 然后我们统计原始数组中小于等于这个中间数的元素的个数为count
        // 假设count大于mid，根据抽屉原理，我们就知道在[1,mid]中一定存在一个抽屉装了超过1个苹果
        // 反之我们就断定[mid+1,n]存在一个抽屉装了超过1个苹果
        // 总体上来说，就是二分搜索算法用于加速划定区间
        // 抽屉原理负责判断重复数落在哪个区间里
        // 算法的时间复杂度为Onlogn，空间复杂度为O1。